#include <iostream>
#include <vector>
using namespace std;

/*****************************************************************************************
*Leecode-2680.cpp -	1表示Leecode第2610题（按照此命名规范编写对应.cpp文件名，目的是方便咱们学生能够快速找到这个Leecode题目，然后可以线上做题）

题目:给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。
    每一次操作中，你可以选择一个数并将它乘 2 。
    你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。
    a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1:
    输入:nums = [12,9], k = 1
    输出:30
    解释:如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2:
    输入:nums = [8,1,2], k = 2
    输出:35
    f解释:如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

解题思路：此题给定一个数组，并给定一个整数k，可以对数组内的任意数进行乘2这样的操作（一共可以执行k次）

在这里我们可能有两种想法，一是对其中一个数进行k次操作，二是对一部分数进行操作。
在这里我们要运用贪心这种想法--就是仅仅对一个数进行操作，证明为：
    如果答案的长度与修改后的 nums[i] 一样长，
    并且我们还修改了其他的数，那么把其他数的乘 2 应用到 nums[i] 上，可以得到二进制更长的数，矛盾。
    所以最优做法是只修改一个数。

将这个想好之后，我们可以想到我们可以对给定的数组进行遍历，即对每一个数都做一遍乘k次2这样的一个操作
然后进行所有数的或值运算。在这里我们定义一个vector<int> temp，运用这个数据存储运算之后的数据，
随后查找最大值即为答案。在处理nums[0]的时候我们可以运用两个for循环嵌套一起进行运算，但是在处理后面的数据的时候
数组一般被分为两个部分这样显然是不行的，所以我们可以想到前缀和以及后缀和

相关知识点：贪心， 前缀和， 后缀和。


*/
class Solution {
public:
    long long maximumOr(vector<int>& nums, int k) {
        long long result = 0;
        int pre = 0;
        int n = (int)nums.size();
        vector<int> temp(n + 1, 0);

        for(int i = n - 1; i >= 0; i--) {
            //在开始创建一个数组存储nums后缀或值
            temp[i] = temp[i + 1] | nums[i];
        }

        for(int i = 0; i < n; i++) {
            //在这里直接遍历并判断最终结果
            //代码解释为，判断当前结果以及下一个可能出现结果哪一个更大，取最大值
            //pre为前缀或值，在i = 0 的时候pre为0，而后缀或值为除第一个元素之外所有数据的或值
            //在这里运用前缀和以及后缀和进行搭配实现所有数据的运算
            result = max(result, pre | ((long long)nums[i] << k) | temp[i + 1]);

            //计算数据前缀或值
            pre |= nums[i];        
        }
        return result;
    }

};